#include <iostream>
#include <vector>
#include <cassert>
using namespace std;

// G_type matrix
typedef vector<vector<int> > G_type;
inline bool reachable(int val){return val!=0;}
bool find_alternative(const G_type& g, vector<int>& link, vector<int>& used, int s)// in the same time reverse the path
{
	if(used[s])return false;
	used[s]=true;
	for(int e=0;e<g.size();e++)
	{
		if(!reachable(g[s][e])) continue;
		if(link[e]==-1 || find_alternative(g, link, used, link[e]))
		{
			link[e]=s;
			return true;
		}
	}
	return false;
}
void bipartite_match(G_type g, vector<int>& link)
{
	int N=g.size();
	fill(link.begin(), link.end(), -1);
	vector<int> used(N, 0);
	for(int i=0;i<N;i++)
		find_alternative(g, link, used, i);
}

// test
G_type gen_g(int N)
{
	G_type g(N);
	for(int i=0;i<N;i++)
		g[i].resize(N);
	return g;
}
void LN(G_type& g, int i, int j)
{
	g[i][j]=g[j][i]=1;
}
int main()
{
	//{
	//	// test correctness
	//	G_type g=gen_g(20);
	//	for(int r=0;r<100;r++)
	//	{
	//		int i=rand()%g.size();
	//		int j=rand()%g.size();
	//		if((i+j)%2==1)
	//			LN(g, i, j);
	//	}

	//	// the same algo like bipartite match
	//	int N=g.size();
	//	vector<int> link(N);

	//	fill(link.begin(), link.end(), -1);
	//	vector<int> used(N, 0);
	//	for(int i=0;i<N;i++)
	//		find_alternative(g, link, used, i);

	//	// this time it should return "false" for all find_argment
	//	for(int i=0;i<N;i++)
	//		assert(!find_alternative(g, link, used, i));
	//}
	{
		G_type g=gen_g(6);
		LN(g, 0,3);
		LN(g, 0,4);
		LN(g, 1,4);
		LN(g, 1,5);
		LN(g, 2,5);
		
		vector<int> link(6);
		bipartite_match(g, link); // 0,3; 1,4; 2,5;
	}
	{
		G_type g=gen_g(6);
		LN(g, 0,3);
		LN(g, 1,3);
		LN(g, 2,3);
		LN(g, 2,5);

		vector<int> link(6);
		bipartite_match(g, link); // 0,3; 2,5;
	}
	{
		G_type g=gen_g(6);// (0,1,2,3), (4,5)
		LN(g,0,4);
		LN(g,1,4);
		LN(g,2,5);
		LN(g,3,5);
		
		vector<int> link(6);
		bipartite_match(g, link); // two
	}	
	return 0;
}